Digital watermarking is a process for modifying physical or electronic media to embed a machine-readable code into the media. The media may be modified such that the embedded code is imperceptible or nearly imperceptible to the user, yet may be detected through an automated detection process. Most commonly, digital watermarking is applied to media signals such as images, audio signals, and video signals. However, it may also be applied to other types of media objects, including documents (e.g., through line, word or character shifting), software, multi-dimensional graphics models, and surface textures of objects.
Digital watermarking systems typically have two primary components: an encoder that embeds the watermark in a host media signal, and a decoder that detects and reads the embedded watermark from a signal suspected of containing a watermark (a suspect signal). The encoder embeds a watermark by altering the host media signal. The reading component analyzes a suspect signal to detect whether a watermark is present. In applications where the watermark encodes information, the reader extracts this information from the detected watermark.
Several particular watermarking techniques have been developed. The reader is presumed to be familiar with the literature in this field. Particular techniques for embedding and detecting imperceptible watermarks in media signals are detailed in the assignee's co-pending application Ser. No. 09/503,881 and U.S. Pat. No. 6,122,403, which are hereby incorporated by reference.
One particular problem in digital watermarking applications is synchronizing a detector to deal with geometric warping distortion of a watermarked image. A number of techniques have been developed for dealing with geometric distortion in watermarked images. One technique is to make the watermark more robust to geometric distortion by embedding it in attributes of the image that are relatively invariant to geometric distortion. While this improves detection in some cases, it typically does not address all forms of geometric distortion and more complex, non-linear geometric distortion. Another technique is to include geometric calibration features in the watermark signal that enable detection and estimation of the geometric distortion parameters, such as rotation and scale. These features include, for example, calibration signal peaks in a particular transform domain, such as the autocorrelation domain and/or Fourier domain. These techniques use correlation techniques or other pattern matching methods to estimate affine geometric distortion parameters. For example, cross correlation of the received signal and the calibration signal in particular transform domains produce correlation peaks that correspond to affine distortion parameters, such as rotation, scale, translation, shear, and differential scale.
Such techniques do not provide error free estimation of geometric distortion. In some cases, errors result from estimation, even where the geometric distortion is linear. In addition, affine transform parameters can only approximate geometric distortion that is non-linear. For example, it can provide a piecewise linear estimate of affine distortion in sub-blocks of an image, but it cannot always accurately represent non-linear distortion in a manner that leads to error free recovery of the digital watermark message.
Similar problems occur in audio watermarking where temporal distortions, such as pitch invariant time scale changes, linear speed changes, up/down sampling, cropping, and lossy compression, make it difficult to synchronize the detector for accurate decoding of embedded message payloads. These and other distortions introduce a form of geometric distortion of the digital watermark signal in the host audio signal.
The invention provides a method for synchronizing a watermark detector. One aspect of the invention is a method of synchronizing a digital watermark detector. The detector operates on a watermarked signal where a watermark signal has been distributed throughout the host media signal, and preferably, repeatedly embedded in segments of the host media signal (e.g., music, image or video signal). The method divides a watermarked signal into blocks, each block including a portion of a watermark signal. For example, in the case where the watermark is replicated in segments of the host signal, these blocks sub-divide each segment into smaller parts. For each block, the method computes a local correlation space comprising a neighborhood of correlation values by correlating the watermarked data in the block with a known watermark signal at a neighborhood around the block. It then finds a correlation maxima in the local correlation space for each block, where the correlation maxima indicates a local offset used to align the watermarked data in the block before decoding a watermark message from the block.
This method applies to watermarked signals of varying media types. In addition, it may be used to synchronize watermark detection and message reading in various signal domains, such as a spatial domain, temporal domain, frequency domain, or some other transform domain (e.g., autocorrelation, wavelet, Fourier, etc.). For example, it can be applied in the spatial domain or spatial frequency domain for images and video frames, as well as the time or frequency domain for audio. It may also be applied in the time-frequency domain for audio and video signals.
In one implementation, the method uses an estimate of affine geometric distortion parameters to transform an image block in the watermarked image to a position approximating an original orientation of the image block in the watermarked image. It then shifts the transformed image block to neighboring locations. The method then computes a correlation surface by finding the correlation between the watermark signal and the transformed block at its location and each of the neighboring locations. The method finds a correlation maximum in the correlation surface formed by the correlation values in the neighborhood. The location of the correlation maximum provides an offset value that further refines the orientation of the image data. A message decoder then decodes a watermark message from the watermarked image adjusted by the offset value.
Further features will become apparent with reference to the following detailed description and accompanying drawings.